/*
 * @lc app=leetcode.cn id=378 lang=cpp
 * @lcpr version=30204
 *
 * [378] 有序矩阵中第 K 小的元素
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        if (k > n * n) return -1;

        // 方法一：暴力求解
        // 将矩阵中的所有元素放入一个数组中，排序后取第 k 小的元素
        // vector<int> res;
        // for (int i = 0; i < n; ++i) {
        //     for (int j = 0; j < n; ++j) {
        //         res.emplace_back(matrix[i][j]);
        //     }
        // }
        // sort(res.begin(), res.end());
        // return res[k - 1];

        // 方法二：最小堆
        // 利用最小堆逐步提取矩阵中的最小元素，直到找到第 k 小的元素
        // priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> minHeap;

        // // 初始化堆，将每行的第一个元素加入堆
        // for (int i = 0; i < n; ++i) {
        //     minHeap.emplace(matrix[i][0], i, 0);
        // }

        // // 提取堆顶元素 k 次
        // int result = 0;
        // for (int i = 0; i < k; ++i) {
        //     auto [val, row, col] = minHeap.top();
        //     minHeap.pop();
        //     result = val;

        //     // 如果当前元素所在行还有下一个元素，将其加入堆
        //     if (col + 1 < n) {
        //         minHeap.emplace(matrix[row][col + 1], row, col + 1);
        //     }
        // }

        // return result;

        // 方法三：二分查找
        // 利用矩阵的有序性，通过二分查找来确定第 k 小的元素
        int left = matrix[0][0], right = matrix[n - 1][n - 1];

        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = countLessEqual(matrix, mid);

            if (count >= k) {
                right = mid; // 第 k 小的元素在左半部分
            } else {
                left = mid + 1; // 第 k 小的元素在右半部分
            }
        }

        return left;
    }

private:
    // 统计矩阵中小于等于 target 的元素个数
    int countLessEqual(const vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int count = 0;
        int row = n - 1, col = 0;

        while (row >= 0 && col < n) {
            if (matrix[row][col] <= target) {
                count += row + 1; // 当前列的所有元素都小于等于 target
                col++;
            } else {
                row--; // 移动到上一行
            }
        }

        return count;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [[1,5,9],[10,11,13],[12,13,15]]\n8\n
// @lcpr case=end

// @lcpr case=start
// [[-5]]\n1\n
// @lcpr case=end

 */

